package com.lun.medium;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.TreeMap;
import java.util.stream.Collectors;

public class ReconstructItinerary {

	//方法一：回溯算法
	public List<String> findItinerary(List<List<String>> tickets) {
		List<String> path = new ArrayList<>();
		Map<String, Map<String, Integer>> flight = ticket2Flight(tickets);
		path.add("JFK");
		backtacking(path, tickets.size(), flight);
		return path;
	}

	private boolean backtacking(List<String> path, int numOfTickets,
			Map<String, Map<String, Integer>> flight) {
		if (path.size() == numOfTickets + 1) {
			return true;
		}

		Map<String, Integer> terminal2NumMap = flight.get(path.get(path.size() - 1));

		if (terminal2NumMap != null) {

			for (Entry<String, Integer> terminal2Num : terminal2NumMap.entrySet()) {

				if (terminal2Num.getValue() > 0) {
					terminal2Num.setValue(terminal2Num.getValue() - 1);
					path.add(terminal2Num.getKey());
					if (backtacking(path, numOfTickets, flight)) {
						return true;
					}
					path.remove(path.size() - 1);
					terminal2Num.setValue(terminal2Num.getValue() + 1);
				}
			}
		}

		return false;
	}

	// Java 8
	private Map<String, Map<String, Integer>> ticket2Flight(List<List<String>> tickets) {
		return tickets.stream().collect(Collectors.groupingBy(ticket -> ticket.get(0), //
				Collectors.groupingBy(ticket -> ticket.get(1), TreeMap::new, //
						Collectors.reducing(0, elem -> 1, Integer::sum))));
	}

	//方法二：DFS
	public List<String> findItinerary2(List<List<String>> tickets) {
		Map<String, PriorityQueue<String>> flights = new HashMap<>();
		List<String> path = new LinkedList<>();

		for (List<String> ticket : tickets) {
			flights.computeIfAbsent(ticket.get(0), k -> new PriorityQueue<>()).add(ticket.get(1));
		}
		dfs("JFK", path, flights);
		return path;
	}

	private void dfs(String departure, List<String> path, Map<String, PriorityQueue<String>> flights) {
		PriorityQueue<String> arrivals = flights.get(departure);
		while (arrivals != null && !arrivals.isEmpty())
			dfs(arrivals.poll(), path, flights);
		path.add(0, departure);
	}

}
